package ru.amse.baltijsky.javascheme.tree.walker;

import ru.amse.baltijsky.javascheme.node.INode;

import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * A depth-first walker for the schema tree. For each node, goes first to its children , then to the next node.
 */
public class DepthFirstTreeWalker<T extends INode<T>> implements ITreeWalker<T> {
    /**
     * The root of the tree to traverse.
     */
    private final T root;
    /**
     * Traversal state that will be returned by the next call to getNextState().
     */
    private TraversalState<T> ret = new TraversalState<T>();
    /**
     * Stack of iterators over branching nodes' children for all currently existing schema tree levels.
     */
    private Deque<Iterator<T>> nodesChildren = new LinkedList<Iterator<T>>();

    /**
     * Contructs a depth-first tree walker that works with the schema tree provided its root.
     *
     * @param theRoot root of the tree to traverse
     */
    public DepthFirstTreeWalker(T theRoot) {
        root = theRoot;
        reset();
    }

    public void reset() {
        ret.node = root;
        ret.prev = null;
        ret.depth = 0;
        ret.rel = TraversalState.Rel.ROOT;
    }

    public boolean hasNextState() {
        return ret.node != null;
    }

    public TraversalState<T> getNextState() {
        if (!hasNextState()) {
            throw new NoSuchElementException();
        }

        // we'll remember current traversal state to return, proceed to the the next node, and return the remembered state
        TraversalState<T> curRet = new TraversalState<T>(ret.node, ret.prev, ret.rel, ret.depth);

        // go to the child first
        if (ret.node.hasChildren()) {
            goToChild();
        } else if (ret.node.hasNext()) {
            goToNext();
        } else {
            goToShallower();
        }

        return curRet;
    }

    /**
     * Goes to the first child of the node and stores the iterator over the other children on the stack.
     */
    private void goToChild() {
        Iterator<T> children = ret.node.getChildren();
        // proceed to the child
        ret.prev = ret.node;
        ret.node = children.next();
        ++ret.depth;
        ret.rel = TraversalState.Rel.CHILD;

        // save the children iterator to traverse the rest of the children later
        nodesChildren.push(children);
    }

    /**
     * Goes to the next node relative to the current.
     */
    private void goToNext() {
        ret.prev = ret.node;
        ret.node = ret.node.getNext();
        ret.rel = TraversalState.Rel.NEXT;
    }

    /**
     * Goes to the node that is the next in the shallower level than the current (used when the current level has ended).
     */
    private void goToShallower() {
        T p = ret.node;
        ret.node = null;
        while (p.hasParent()) {
            p = p.getParent();
            if (p.hasChildren()) { // proceed to the next child of the node-with-children
                if (nodesChildren.peek().hasNext()) {
                    ret.rel = TraversalState.Rel.CHILD;
                    ret.node = nodesChildren.peek().next();
                    ret.prev = p;
                    break;
                } else {
                    nodesChildren.pop();
                }
            }
            --ret.depth;
            if (p.hasNext()) {
                ret.prev = p;
                ret.node = p.getNext();
                ret.rel = TraversalState.Rel.NEXT;
                break;
            }
        }
    }
}
    